package org.concepts.algorithm.sort;

import org.concepts.algorithm.utils.MathUtils;

/**
 * <a href="http://en.wikipedia.org/wiki/Bubble_sort">BubbleSort</a>
 * 
 * @author vvvv
 * 
 * @param <E>
 */
public class BubbleSort<E extends Number> implements Sorter<E> {

  /**
   * In bubble sort we compare each element in the array with the next element
   * and if the element is greater than the next then swap the element. Keep
   * doing this till we don't have to swap any element. After we have gone 
   * through the whole array once, the largest number will move to the
   * bottom, thus for the next time we only need to look at n - 1. Thus 
   * after each pass we can look at n - pass elements to sort.
   * <p/>
   * 
   * Average/Worst case: O(n^2) as we go through the list n times and for each
   * iteration we do no comparison. Best case: O(n) if the list is almost
   * sorted.
   */
  @Override
  public E[] sort(E[] input) {
    int pass = 0;
    // go through input n times
    while (true) {
      boolean swap = false;
      pass++;
      // for each iteration swap element if one on left is greater than
      // one on right
      for (int inputCnt = 0; inputCnt < input.length - pass; inputCnt++) {
        if (MathUtils.compare(input[inputCnt], input[inputCnt + 1]) > 0) {
          MathUtils.swap(input, inputCnt, inputCnt + 1);
          swap = true;
        }
      }

      if (!swap) {
        // we have a sorted list, time to break out
        break;
      }
    }
    return input;
  }

}
